package medium;

import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;

/**
 * Created by daodao on 2017/12/8.
 * Problem 12
 * Description: Given an integer, convert it to a roman numeral.
 * Input is guaranteed to be within the range from 1 to 3999.
 */
public class IntegerToRoman {
    public static String intToRoman(int num) {
        StringBuilder romanNum = new StringBuilder();
        Map<Integer, Character> romanMap = new TreeMap<>();
        romanMap.put(1, 'I');
        romanMap.put(10, 'X');
        romanMap.put(100, 'C');
        romanMap.put(1000, 'M');
        romanMap.put(5, 'V');
        romanMap.put(50, 'L');
        romanMap.put(500, 'D');
        int digit = num;
        int quotient;
        int divisor = 1000;
        while (divisor >= 1 && digit >= 1) {
            quotient = digit / divisor;
            if (quotient == 0) {
                divisor /= 10;
                continue;
            } else if (quotient > 0 && quotient < 4) {
                int count = quotient;
                while (count > 1) {
                    romanNum.append(romanMap.get(divisor));
                    count--;
                }
                romanNum.append(romanMap.get(divisor));
            } else if (quotient == 4) {
                romanNum.append(romanMap.get(divisor));
                romanNum.append(romanMap.get(5 * divisor));
            } else if (quotient == 5) {
                romanNum.append(romanMap.get(5 * divisor));
            } else if (quotient == 9) {
                romanNum.append(romanMap.get(divisor));
                romanNum.append(romanMap.get(10 * divisor));
            } else {
                romanNum.append(romanMap.get(5 * divisor));
                int count = quotient;
                while (count > 5) {
                    romanNum.append(romanMap.get(divisor));
                    count--;
                }
            }
            if (digit < 10) {
                break;
            }
            digit %= divisor;
        }

        return romanNum.toString();
    }
}
